#include<string.h>
#include<algorithm>
#include<limits.h>
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
//1.判断素数
//素数:除了1和本身，不能被其它数整除
bool isPrime(int n)
{
    //n试除[2,n-1]的数
    for(int i = 2;i<n;i++)
        if(n % i == 0)
            return false;
    return true;
}
//假设 m = a*b  a和b至少有一个是<=sqrt(m)的,所以只需要试除到sqrt(n)
bool isPrime_2(int n)
{
    for(int i = 2;i<=sqrt(n);i++)
        if(n % i == 0)
            return false;
    return true;
}

//2.判断闰年 4年一闰&&百年不闰  || 400年又一闰
bool LeapYear(int year)
{
    return ((year % 4 == 0) && (year % 100 != 0))  || (year % 400 == 0);
}

//3.10进制数转为6进制
void ConverBaseSix(int n)
{
  vector<int> v;
  while(n)
  { 
    v.push_back(n % 6);
    n /= 6;
  }
  //倒着打印
  for(int i = v.size()-1;i>=0;i--)
    cout << v[i] << " ";
  cout << endl;
}
//4.一瓶汽水1元,2个空瓶可以换一瓶汽水,问：money元可以喝多少瓶水
int Coco(int money)
{
  int total = money; //能喝多少瓶
  int empty = total;//空瓶个数
  while(empty >= 2)
  {
    total += empty / 2; //总数加上用空瓶换来的汽水
    empty = empty / 2 + empty % 2;//现在的空瓶个数 = 用空瓶换来的汽水 + 不够换汽水的空瓶
  }
  return total;
}
//5.有效序列判断
bool isValidSequence(vector<int>& v)
{
  int flag1 = 0,flag2 = 0; //flag1：标志升序  flag2：标志降序
  for(size_t i = 1;i<v.size();i++)
  {
    if(v[i] > v[i-1]) //升序
      flag1 = 1;
    else 
      flag2 = 1;
  }
  //判断是否是有效序列->恒为升序/降序 ==>flag1 + flag2 = 1
  if(flag1 + flag2 == 1)
    return true;
  else 
    return false;
}
//6.猜凶手
/*
    4个嫌疑犯的供词：A说:不是我 B说：是C  C说:是D  D说:C在胡说
    已知3个人说了真话,1个人说了假话,写程序确定谁是凶手
*/
void GuessMurDerer()
{
  //穷举法,从A~D穷举
  //三个人说了真话,一个人说了假话  ==>条件相加为3
  for(char killer = 'A';killer <='D';killer++)
  {
    if((killer != 'A') + (killer == 'C') + (killer == 'D') + (killer != 'D') == 3)
      cout << "凶手是 "  << killer << endl;
  }
}
//7.模拟实现atoi
enum State
{
  VALID, //有效
  INVALID //异常
};
//对于空指针/str为空串/溢出  参数为"0"的情况都是返回0,但是前者是异常返回,后者是正常返回
//所以需要定义一个全局变量来标识是否是正常返回
enum State state = INVALID; //假设异常返回
int my_atoi(const char* str)
{
  if(str == NULL || *str == '\0')
  {
    return 0;
  }
  //1.先跳过前面的空格
  while(isspace(*str))
    str++;
  //2.判断是否有符号
  int flag = 1; //假设是正数
  if(*str == '+')
  {
    flag = 1,str++;//注意:str需要往后走
  }
  else if(*str == '-')
  {
    flag = -1,str++;
  }
  //注意：上述不能使用if-else的逻辑,因为不一定有符号
  
  //3.转换
  long long res = 0;//因为可能溢出,所以定义为long long 类型
  while(*str)
  {
    //如果遇到非数字字符,就不需要继续转化, 此时属于正常返回
    if(!isdigit(*str))
    {
      state = VALID;
      return (int)res;
    }
    res  = res * 10 + (*str - '0') * flag;
    //判断是否溢出
    if(res > INT_MAX || res < INT_MIN)
      return 0;
    str++;
  }
  //一切正常
  state = VALID;
  return (int)res;
}

/*  //Leetcode测试:https://leetcode.cn/problems/string-to-integer-atoi/submissions/
class Solution {
public:
    int myAtoi(string s) {
    const char* str = s.c_str();
       if(*str == '\0') 
            return 0;
       //1.跳过前缀空格
       while(isspace(*str))
            str++;
        //2.判断有无符号位
       int flag = 1;
       if(*str == '+')
            flag = 1,str++;
       else if(*str == '-')
            flag = -1,str++;
        //3.转换
        long long res = 0;
        while(*str)
        {
            if(!isdigit(*str))
            {
                return (int)res;
            }
            else 
            {
                res = res * 10 + (*str - '0') * flag;
                if(res > INT_MAX) return INT_MAX;
                if(res < INT_MIN) return INT_MIN;
            }
            str++;
        }
        return (int)res;
    }
};
*/
//8.写一个宏交换一个数的奇偶位
//5:0101    10: 1010
//假设最低位为偶数位(第0位),那么获取偶数位: 0x55555555  获取奇数位:0xaaaaaaaa
// (偶数位<<1) + (奇数位 >> 1) 就交换了奇偶位
#define SWAPBIT(n)   (((n)&0x55555555) << 1 )  + (((n)&0xaaaaaaaa) >> 1)

//9.Sn = a + aa + aaa + ....//n项相加
void TernAdd(int a,int n) //a:值  n:项数
{
  int k = 0;//当前项
  int sum = 0;//累加值
  for(int i = 0;i<n;i++)
  {
    k = k*10 + a; //第一轮:a  第二轮:aa ...
    sum += k;
    if(i != n-1)
      cout << k  <<" + " ;
    else 
      cout << k << " = " << sum << endl;
  }
}

//10.猜名次
/*
    A选手说:B第二 我第三
    B选手说:我第二,E第四
    C选手说:我第一,D第二
    D选手说:C最后,我第三
    E选手说:我第四,A第一
    每位选手只说对了一半,请确定比赛的名次
*/
void GuessPlace()
{
   //名次范围:1~5 
   for(int A = 1;A<=5;A++)
   {
     for(int B = 1;B<=5;B++)
     {
       for(int C = 1;C<=5;C++)
       {
         for(int D = 1;D<=5;D++)
         {
           for(int E = 1;E<=5;E++)
           {
              int flag1 = ((A == 3) + (B == 2)  == 1) ;
              int flag2 = ((B == 2) + (E == 4)  == 1) ;
              int flag3 = ((C == 1) + (D == 2)  == 1) ;
              int flag4 = ((C == 5) + (D == 3)  == 1) ;
              int flag5 = ((E == 4) + (A == 1)  == 1) ;
              if(flag1 + flag2 + flag3 + flag4 + flag5 == 5)
              {
                if(A*B*C*D*E == 120)
                  cout <<"A~E的范围是 " <<  A << " " << B <<" "<< C <<" "<<D << " " << E << endl; 
              }
           }
         }
       }
     }
   }
}



//11.字符串左旋
//abcd,2  ==> cdab
string LeftRotation(string s,int k)
{
    string str = s;
    int n = str.size();
    k %= n; 
    //三步逆置法
    //1.前k个字符逆置
    //2.后n-k个字符逆置
    //3.整体逆置
    reverse(str.begin(),str.begin()+k);//reverse函数:左闭右开
    reverse(str.begin()+k,str.end());
    reverse(str.begin(),str.end());
    return s;
}

//12.旋转结果判断 判断一个字符串是不是另一个字符串左旋得到的结果
bool JudgeLeftRoationResult_version1(string s1,string s2)
{
    int n = s1.size();
    if(s1.size() != s2.size())
        return false;
    //方法1:s1不断左旋1个字符,然后判断左旋结果是否和s2相同,共旋转s1.size()个字符次
    for(int i = 0;i<n;i++)
    {
      if(LeftRotation(s1,i) == s2)
        return true;
    }
    return false;
}

bool JudgeLeftRoationResult_version2(string s1,string s2)
{
  if(s1.size() != s2.size())
      return false;
  //方法2:在s1后追加s1, 然后以s1为主串 找子串s2
  int n = s1.size();
  char* buf = new char[n*2+1];
  strcpy(buf,s1.c_str());
  //追加- 不能用strcat 要用strncat
  strncat(buf,buf,n); 
  bool flag =  strstr(buf,s2.c_str()) != nullptr;
  //不能直接return  strstr(....) ,否则会造成内存泄露！！！
  delete[] buf;
  return flag;
}


bool YoungTableau(vector<vector<int>>& v,int target)
{
  //右上角元素:第一行最大的,最后一列最小的
  //左下角元素:最后一行最小的,第一列最大的  
  //一次排除1行 /  1列
  //此处采用右上角元素来做: (0,v[0].size()-1)
  int row = v.size();
  int col = v[0].size();
  int xStart = 0;
  int yStart = col-1;
  while(xStart <= row-1 && yStart >= 0)
  {
    if(target > v[xStart][yStart])
    {
      xStart++; //这一行找不到了
    }
    else if(target < v[xStart][yStart])
    {
      yStart--;//这一列找不到了
    }
    else 
      return true;
  }
  return false;
}

int main()
{
   // for(int i = 1900;i<=2000;i++)
   // {
   //     if(isPrime(i) != isPrime_2(i))
   //         cout <<"出错了"<<endl;

   //     if(LeapYear(i))
   //         cout << i << endl ; 
   // }
    
    return 0;
}
